#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<list>
#include<stdio.h>
#include<vector>
using namespace std;
//int main()
//{
//
//	int ar[] = { 0,1, 2, 3, 4,  5, 6, 7, 8, 9 };
//
//	int n = sizeof(ar) / sizeof(int);
//
//	list<int> mylist(ar, ar + n);
//
//	list<int>::iterator pos = find(mylist.begin(), mylist.end(), 5);
//
//	reverse(mylist.begin(), pos);
//
//	reverse(pos, mylist.end());
//
//	list<int>::const_reverse_iterator crit = mylist.crbegin();
//
//	while (crit != mylist.crend())
//
//	{
//
//		cout << *crit << " ";
//
//		++crit;
//
//	}
//
//	cout << endl;
//	return 0;
//
//}
#include<stack>
#include<iostream>
//class Solution
//{
//public:
//
//    bool IsPopOrder(vector<int>& pushV, vector<int>& popV)
//    {
//        auto push_it = pushV.begin();
//        auto pop_it = popV.begin();
//        while (push_it != pushV.end())
//        {
//            if (*push_it != *pop_it)
//            {
//                mystack.push(*push_it);
//                ++push_it;
//            }
//            else
//            {
//                ++push_it;
//                ++pop_it;
//            }
//        }
//        while ((!mystack.empty()) && mystack.top() == *pop_it)
//        {
//            mystack.pop();
//            ++pop_it;
//        }
//        return mystack.empty();
//
//    }
////    stack<int> mystack;
////};
//class Solution
//{
//public:
//
//    bool IsPopOrder(vector<int>& pushV, vector<int>& popV)
//    {
//        auto push_it = pushV.begin();
//        auto pop_it = popV.begin();
//        while (push_it != pushV.end())
//        {
//            if (*push_it != *pop_it)
//            {
//                mystack.push(*push_it);
//                ++push_it;
//            }
//            else
//            {
//                mystack.push(*push_it);
//                while ((!mystack.empty()) && mystack.top() == *pop_it)
//                {
//                    mystack.pop();
//                    ++pop_it;
//                }
//                if (push_it != pushV.end())
//                    push_it++;
//
//            }
//        }
//        while ((!mystack.empty()) && mystack.top() == *pop_it)
//        {
//            mystack.pop();
//            ++pop_it;
//        }
//        return mystack.empty();
//
//    }
//    stack<int> mystack;
//};
#include<vector>
#include <utility> 
using namespace std;
class Solution {
public:
    void AdjustDown(vector<int>& nums, int parent, int size)
    {
        int lchild = parent * 2 + 1;
        while (lchild<=size)
        {
            int rchild = lchild + 1;
            if (rchild<=size && nums[rchild] < nums[lchild])
            {
                lchild++;
            }
            if (nums[lchild] < nums[parent])
            {
                swap(nums[lchild], nums[parent]);
                parent = lchild;
                lchild = parent * 2 + 1;

            }
            else
                break;
        }

    }
    int findKthLargest(vector<int>& nums, int k)
    {

        for (int i = (k - 2) / 2;i >= 0;--i)
        {
            AdjustDown(nums, i, k - 1);
        }
        for (int j = k;j < nums.size();++j)
        {
            if (nums[j] > nums[0])
            {
                swap(nums[j], nums[0]);
                AdjustDown(nums, 0, k - 1);
            }

        }
        return nums[0];
    }

};
int main()
{
    list<int> lt = { 1,2 };
    vector<int> a = { 3,2,1,6,6,4 };
    vector<int> b = { 4,5,3,2,1 };
    cout << Solution().findKthLargest(a, 2);
}